As is known in the art, it is frequently desirable to detect and segment an image into meaningful regions, allowing for instance to distinguish an object from a background of other objects and/or from a background of noise. One application, for example, is in CT or MRI where it is desired to segment an anatomical feature of a human patient, such as, for example, a vertebra of the patient. In other cases it would be desirable to segment a moving, deformable anatomical feature such as the heart.
As is also known in the art, a watershed transform, originating in the field of topography, is a traditional tool of mathematical morphology used to partition an image into disjoint regions with homogeneous intensity values. A watershed segmentation algorithm typically consists of defining an elevation map corresponding to the image gradient magnitude, and computing its catchment basins through immersion or rain fall simulations.
A known issue with this technique is that noise, as well as other variations of intensity that do not correspond to object boundaries, produce spurious local minima in the image gradient magnitude which result in oversegmentation. This phenomenon is illustrated in FIGS. 1(a) to 1(f) with a CT image FIG. 1a, its gradient magnitude FIG. 1b and the corresponding watershed regions FIG. 1c. 
One way to mitigate this problem is to select, interactively or automatically, specific minima that yield catchment basins corresponding to the desired objects. Another simple solution is to regularize the gradient image to limit its number of extrema. An example is shown where the gradient image is filtered with a Gaussian kernel FIG. 1e and a new watershed partition is computed FIG. 1f. While a more meaningful segmentation is obtained, additional steps would still be required to produce an anatomically relevant labeling of the image. A thorough discussion on the combination of multiscale analysis and watersheds is available in a paper entitled by J. Gauch entitled Image segmentation and analysis via multiscale gradient watershed hierarchies. IEEE Transactions on Image Processing, 8(1):69-79, 1999.
Another strategy consists of considering the initial watershed regions as building blocks that can be assembled to produce a higher level description of the data. The starting point for such methods is the adjacency graph of the watershed regions. Introducing edge-weights corresponding to region dissimilarity measures, one can easily obtain a series of segmentations by selecting and merging iteratively neighboring regions with the highest affinity. A fast implementation of this approach is discussed in Hybrid image segmentation using watersheds and fast region merging. IEEE Transactions on Image Processing, 7(12):1684-1699, 1998 by Haris et al. In the same setting, one can also formulate the grouping of watershed regions as a labeling of the adjacency graph, using for instance a Markovian relaxation method as described in Segmenting internal structures in 3D MR images of the brain by Markovian relaxation on a watershed based adjacency graph. In Proceedings of ICIP 1995, pages 548-55 1, 1995 by Geraud et al. FIG. 1 illustrates the iterative region merging method, starting with the partition shown in FIG. 1c and arbitrarily stopping when 8 regions remain. Assuming the goal is to segment the image into anatomical regions, this result appears more satisfactory than partition FIG. 1f. However, such a fully automated approach allows little flexibility to incorporate application-specific knowledge. What if, in the previous example, the user also wants to segment the heart from the rest of the soft tissue?
It is first noted that the number of watershed regions in the CT image shown is less than 10% its number of pixels. Similar results can be observed on a broad range of real images. These regions provide a decomposition of the image into building blocks that appear very suitable for segmentation tasks: they do not cross over image boundaries and contain pixels with similar intensity values. Based on these observations, we use here the watershed transform as a “morphological” dimensionality reduction step for graph-based segmentation algorithms. In addition, we choose to incorporate prior knowledge by constraining the segmentation process with markers scribbled by the user over various regions of interest and their background.
Adding interactivity and user inputs to guide the segmentation seems to be a natural solution to this problem. Starting with the intelligent scissors algorithm described in Interactive segmentation with intelligent scissors. Graphical Models and Image Processing, 60(5):349-384, 1998 by Mortensen et al., an increasing body of work is now dedicated to semi-automatic techniques for image segmentation.
As is also known in the art, one technique used in object segmentation uses algorithms based on seeds (or scribbles or marks) placed by the user over regions of interest (i.e., the object). The “graph cuts” algorithm described in “Interactive graph-cuts for optimal boundary and region segmentation of objects in N-D images” In Proceedings of ICCV 2001, pages 105-112, 2001 by Boykov et al, for instance, finds a minimum weight cut between foreground and background seeds set by the user on the image lattice. A multilabel partitioning method based of the probability that a “random walker” evolving on the image first reaches a seed with a given label has been described by Grady in Random walks for image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(11): 1768-1783, 2006. A third method is the marker-based geodesic partitioning algorithm implemented by Protiere and Sapiro, see Interactive image segmentation via adaptive weighted distances. IEEE Transactions on Image Processing, 16(4): 1046-1057, 2007, using linear time Hamilton-Jacobi solvers.
In accordance with the present invention, a method is provided for segmenting at least a pair of regions of an image, such method comprising: obtaining data of the image; computing watersheds of the image from intensity gradients of such image data; extracting a watershed region adjacency graph from the computed watersheds, such graph comprising a plurality of nodes corresponding to the watersheds and node interconnecting edges; assigning weights to the interconnecting edges; identifying each of the pair of regions in the image; identifying the nodes corresponding to the pair of identified regions in the adjacency graph; applying constrained graph-partitioning in the adjacency graph using the edge-weights to label unmarked nodes corresponding to each one of the pair of regions; and extrapolating the obtained label nodes on the graph to the image to segment each one of the pair of regions of the image.
In one embodiment, the constrained graph-partitioning comprises using competing wavefronts, each one of the wavefronts emanating from a corresponding node and propagating outwardly from such node to interconnected nodes at a rate related to the edge weights interconnecting such nodes.
In one embodiment, the constrained graph-partitioning comprises using a random walker algorithm. In this embodiment the random walker algorithm comprises: defining regions containing markers as internal boundaries; computing the Laplacian matrix of the adjacency graph using the edge-weights to produce probability maps; and partitioning the adjacency graph using the probability maps.
Thus, instead of performing the segmentation in the original image data domain where a pixel-by-pixel analysis is performed using a comparison of intensity differences between adjacent pixels, here, in accordance with the invention, segmentation is performed in the adjacency graph domain and then the segmented region on the graph is transformed back into the original image data domain. That is, the user identifies large plural pixel regions of similar intensity using watersheds and then constructs the adjacency graph where the plural pixel watersheds are identified as nodes and where contiguous nodes are interconnected with weighted edges related to relative intensity between adjacent watersheds (i.e., plural containing pixel nodes). The user identifies the region of interest in the original image data domain with one type of mark and unwanted adjacent to the regions of interest with a different type of mark. The seed marks in the region of interest are expanded and the seeds marks in the unwanted region are also expanded until they collide at the boundary or border of the desired region to thereby segment the desired region of interest from the unwanted regions. This segmentation process is this performed in the adjacency graph domain and then, once segmented in the adjacency graph the segmented region transformed into the original image data domain. The relative intensity data is contained in the adjacency graph by the edge weights. The process of expanding each of the regions to include other node in the region of interest and those in the unwanted regions is performed by constrained graph partitioning. In one embodiment competing wavefronts is used, each one of the wavefronts emanating from a corresponding node and propagating outwardly from such node to interconnected nodes at a rate related to the edge weights interconnecting such nodes. In another embodiment, the constrained graph-partitioning comprises uses a random walker algorithm. In this embodiment the random walker algorithm comprises: defining regions containing markers as internal boundaries; computing the Laplacian matrix of the adjacency graph using the edge-weights to produce probability maps; and partitioning the adjacency graph using the probability maps.
The details of one or more embodiments of the invention are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the invention will be apparent from the description and drawings, and from the claims.
Like reference symbols in the various drawings indicate like elements.